package com.desheng.bigdata.ds.queue;
/*
    最小优先级堆，可以看做是最大优先级的反向，只要保证第一个元素是集合中最小即可
 */
public class MinPriorityQueue<T extends Comparable<T>> {
    //队列的长度
    private int size;
    private T[] items;//存放队列元素的数组

    private static final int DEFAULT_CAPACITY = 10;
    public MinPriorityQueue(int capacity) {
        this.items = (T[])new Comparable[capacity + 1];//第一个节点不存储元素
    }

    public MinPriorityQueue() {
        this.items = (T[])new Comparable[DEFAULT_CAPACITY + 1];//第一个节点不存储元素
    }
    /*
        元素入队其实，就是把该元素放入到堆中合适的位置
     */
    public void enqueue(T data) {
        if(size == items.length - 1) {
            T[] newObjs = (T[])new Comparable[items.length + items.length / 2];
            System.arraycopy(items, 1, newObjs, 1, size);
            items = newObjs;
        }
        items[++size] = data;
        //插入元素之后调整该元素
        rise(size);
    }

    /*
        上浮index索引位置处的元素到执行的位置
        该元素如何和自己的父节点比较，比父节点大，二者就要交换位置
     */
    private void rise(int index) {
        while (index > 1) {
            if(!less(index, index / 2)) {
                break;
            }
            exchange(index, index / 2);
            index = index / 2;

        }
    }

    //从队列中移除优先级最低的元素
    public T dequeue(){
        T min = items[1];
        exchange(1, size--);//交换相关元素
        sink(1);//下沉，将最小的元素调整到最小的位置
        return min;
    }

    /*
        将index位置处的元素开始调整，使之成为一个堆
     */
    private void sink(int index) {
        while (2 * index <= size) {
            int min = 2 * index;
            if((min + 1) <= size) {
                if(less(min + 1, min)) {
                    min = min + 1;
                }
            }
            if(less(index, min)) {
                break;
            }
            exchange(index, min);
            index = min;
        }
    }

    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }
}
